# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        father = {}
        def f(root, parent):
            if not root: return
            father[root] = parent
            f(root.left, root)
            f(root.right, root)
        f(root, None)
        res = []
        def dfs(node, come, depth):
            if not node: return
            if depth == k:
                res.append(node.val)
            if node.left != come:
                dfs(node.left, node, depth + 1)
            if node.right != come:
                dfs(node.right, node, depth + 1)
            if father[node] != come:
                dfs(father[node], node, depth + 1)
        dfs(target, None, 0)
        return res
